package sol.leetcode;

/**
 * First Bad Version
 */
public class Issue278 {
    public int firstBadVersion(int n) {
        if (n == 1)
            return 1;

        int p = 1;
        int q = n;
        int m = (p + q) / 2;

        while (!(p == q || p == q - 1)) {
            if (!isBadVersion(m))
                p = m + 1;
            else
                q = m;
            m = (int) (((long) p + q) / 2);
        }

        if (isBadVersion(p))
            return p;
        return q;

        //参考
        //int start = 1, end = n;
        //while (start < end) {
        //    int mid = start + (end-start) / 2;
        //    if (!isBadVersion(mid)) start = mid + 1;
        //    else end = mid;
        //}
        //return start;
    }

    public boolean isBadVersion(int n) {
        if (n < 1702766719)
            return false;
        return true;
    }

    public static void main(String[] args) {
        Issue278 sol = new Issue278();
        System.out.println(sol.firstBadVersion(2126753390));
    }
}
